\chapter{Wstęp teoretyczny do problemu szeregowania zadań}
\thispagestyle{fancy}
  \section{Wprowadzenie do problemu}

    Problem szeregowania zadań jest często spotykany we współczesnym świecie. Znajduje on swoje odzwierciedlenie m.in. w fabrykach - wszelkiego rodzaju linie produkcyjne, szkołach - układanie planu zajęć, jak również w wielu dziedzinach informatyki, np. wielozadaniowość w systemach operacyjnych - przydzielanie czasu procesora. Szeregowanie zadań jest problemem \textbf{NP}-trudnym, dlatego intensywnie poszukiwane są algorytmy, które efektywnie przybliżają dokładne rozwiązanie. W naszej pracy zaimplementowaliśmy i przetestowaliśmy cztery algorytmy: \textbf{pszczeli} (\textit{discrete artificial bee colony algorithm}), \textbf{świetlika} (\textit{glowworm swarm optimization}) oraz \textbf{roju cząstek} (\textit{particle swarm optimization}) (ich zasada działania została szczegółowo omówiona w kolejnych rozdziałach).

  \section{Opis problemu}
    \subsection{Dane wejściowe}
      
      W problemie szeregowania zadań istnieją dwa zbiory:
      \begin{itemize}
       \item $J={J_1,J_2,...,J_n}$ - zbiór $n$ zadań (\textit{jobs}), które będziemy szeregować
       \item $M={M_1,M_2,...,M_m}$ - zbiór $m$ maszyn (\textit{machines}) wykorzystywanych do wykonywania poszczególnych zadań
      \end{itemize}

      Inne parametry opisujące zbiór zadań $J$:
      \begin{itemize}
       \item $\pi$ - dane rozwiązanie (permutacja $n$-elementowa)
       \item $p_{\pi_i,j}$ - czas obróbki $i$-tego zadania na $j$-tej maszynie
       \item $C(\pi_i,j)$ - czas zakończenia $i$-tego zadania na $j$-tej maszynie
       \item $C(\pi_N,M)$ - kryterium optymalizacyjne (jedno z kilku - w tym przypadku $C_{max}$ - opisane w dalszej części)
      \end{itemize}
      
      W zbiorze $J$ mogą występować różne zależności kolejnościowe, tworzące relację częściowego porządku, na przykład rozpoczęcie zadania $J_i$ może się zacząć wtedy i tylko wtedy, gdy zadanie $J_k$ już się zakończyło. Zadania są \textbf{zależne} jeśli w zbiorze występują zależności, w przeciwnym wypadku zadania są \textbf{niezależne}.

      Mówimy, że zadanie jest \textbf{podzielne} jeśli może zostać przerwane, w innym przypadku jest \textbf{niepodzielne}.

      Problem szeregowania zadań jest deterministyczny jeśli zadane są z góry powyższe warunki.

      Zadania są wykonywane na stanowiskach roboczych:
      \begin{itemize}
       \item \textbf{równoległych} - spełniających te same funkcje, zadanie może zostać wykonane na dowolnej maszynie
       \item \textbf{dedykowanych} - różniących się wykonywanymi funkcjami.
      \end{itemize}
      
      W naszym projekcie zajmujemy się tylko stanowiskami dedykowanymi. Oznacza to, że każde z zadań $J$ jest podzielone na $m$ niepodzielnych operacji $O_{i,j}$, z których każda jest przypisana do konkretnej maszyny $M_j$. Czas wykonywania danej operacji oznaczamy analogicznie - $p_{\pi_i,j}$. Dane zadanie $J$ nie musi wykorzystywać wszystkich maszyn ze zbioru $M$ (wtedy $p_{\pi_i,j}=0$). Podobnie, jak w zbiorze zadań, w zbiorze operacji dla danego zadania mogą występować zależności kolejnościowe. Mówimy, że zadanie zostało wykonane, jeżeli wszystkie jego operacje zostały wykonane.
      
    \subsection{Dane wyjściowe}
      
      Rozwiązaniem problemu szeregowania zadań jest znalezienie optymalnego uszeregowania zadań ze względu na zadaną funkcję celu. Uszeregowanie musi spełniać następujące warunki:
      
      \begin{itemize}
       \item w każdej chwili dana maszyna wykonuje conajwyżej jedną operację (zadanie)
       \item w każdej chwili dane zadanie jest wykonywane co najwyżej na jednej maszynie
       \item wszystkie zadania zostaną wykonane przed upływem terminu krytycznego dla danego zadania (jeżeli został on określony)
       \item jeżeli zadanie jest niepodzielne, to jest wykonywane nieprzerwanie, jeżeli jest podzielne, to liczba przerw jest skończona
       \item wszystkie ograniczenia kolejnościowe są zachowane	

      \end{itemize}

    \subsection{Funkcja celu - kryterium optymalizacyjne}
      
      Kryterium optymalizacyjne oznacza sposób w jaki dokonujemy wyboru rozwiązania. W praktyce oznacza to poszukiwanie minimum lub maksimum zadanej funkcji. Najczęściej spotykanymi kryteriami optymalizacyjnymi są:
      
      \begin{itemize}
       \item $C_{max}=max_{i=1,2,...,n}{C_i}$ - \textit{makespan}, długość uszeregowania
       \item $\overline{F}=\frac{\sum\limits_{i=1}^{n}F_i}{n}$ - \textit{average flow time}, średni czas przepływu
       \item $T_{max}=max_{i=1,2,...,n}{C_i}$ - \textit{maximum tardiness}, maksymalne spóźnienie
       \item $\overline{T}=\frac{\sum\limits_{i=1}^{n}T_i}{n}$ - \textit{average tardiness}, średnie spóźnienie
      \end{itemize}

    \subsection{Typy systemów obsługi}
    
      Dla maszyn dedykowanych wyróżnia się trzy systemy obsługi:
      \begin{itemize}
       \item otwarty (\textit{open shop}) - każde zadanie musi być wykonywane przez wszystkie maszyny ale kolejność wykonywania nie jest narzucona,
       \item przepływowy (\textit{flow shop}) - każde zadanie musi być wykonywane w tej samej kolejności przez wszystkie maszyny,
       \item ogólny (\textit{job shop}) – podzbiór maszyn mających wykonać dane zadanie oraz kolejność wykonywania każdego zadania są dowolne, choć określone.
      \end{itemize}
      
      W naszej pracy będziemy się zajmować tylko najprostszym przypadkiem - \textit{zagadnieniem permutacyjnym flowshop}.

    \subsection{Problem flowshop}
      \subsubsection{Opis problemu}
	
	Jak już wcześniej zostało wspomniane jest to najprostszy typ wykorzystywany w problemie szeregowania zadań. Przyjmujemy w nim, że każde zadanie składa się z tych samych operacji, które zawsze muszą być wykonywane w identycznym porządku. Oznacza to, że każde zadanie musi przejść przez wszystkie maszyny w ściśle określonym porządku. W naszym projekcie dodatkowo zalożyliśm, że nasz problem jest \textit{permutacyjny}, czyli zadania muszą być wykonane w tej samej kolejności na każdej z maszyn.

      \subsubsection{Klasyfikacja}
      
      \subsubsection{Przykład}
	
	Mamy dany problem permutacyjny $F3||C_{max}$. Dane wejściowe to $M=({M_1,M_2,M_3})$ - mamy 3 maszyny oraz $J_1=({4,2,1}), J_2=({3,6,2}), J_3=({7,2,3}), J_4=({1,5,8})$. Dane wyjściowe to \textbf{wykres Gantta} jak na rysunku poniżej:
	
	\begin{figure}[H]
	  \centering \includegraphics[width=0.8\textwidth]{pics/wstep/gantt.png}
	  \caption{Rozwiązanie problemu $F3||C_{max}$ w postaci wykresu Gantta.}
	\end{figure}
